package algorithm.difficult;

import java.util.Arrays;

/**
 * 一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。
 * <p>
 * 给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 109 + 7 取余 后的结果。
 * <p>
 * 子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。
 * <a href="https://leetcode.cn/problems/sum-of-subsequence-widths/solutions/1977772/by-muse-77-f6s5/">...</a>
 */
public class sumSubseqWidths891 {

    public int sumSubseqWidths(int[] nums) {
        long result = 0;
        int len = nums.length;
        //排序。每个子序列最大最小元素，即使跟顺sor只考虑两个点
        Arrays.sort(nums);
        //下标i 所贡献的最大值和最小值次数的差值*该值 即是该数对结果的贡献
        //担任最大值次数 2^i  担任最小值次数 2^(length-i-1)
        //由于2的n次方很大，初始化2^n的值。并且取余
        long[] pow = new long[len];
        int mod = (int) (1e9 + 7);
        pow[0] = 1;
        for (int i = 1; i < len; i++) {
            pow[i] = (pow[i - 1] << 1) % mod;
        }
        for (int i = 0; i < nums.length; i++) {
            result = (result + ((pow[i] - pow[len - i - 1]) * nums[i]) % mod) % mod;
        }
        return (int) result;
    }

}
